1. Field of the Invention
The present invention relates to the field of information processing, and more particularly to a data-driven information processing device that carries out execution of an instruction when all data required for the execution of an instruction are available.
2. Description
It is considered that the data driven principle is essentially a natural information processing system. A data-driven processor with this data driven principle as the basic principle is a general term of a series of processors developed from a research plan directed to effectively execute a subject program directly converted from a high level specification description that can be executed.
The data driven principle is set forth in the following. A program is formed of a plurality of instructions. Each instruction attains an executable state when all argument data required for each execution have arrived in the form of a token (data packet). An instruction attaining an executable state is provided to an operation processing mechanism together with its argument data and destination of the executed result.
The process of determination of whether an instruction attains an executable state or not and sending an instruction, if executable, to an operation processing mechanism together with the argument data and destination of result is carried out by a firing control mechanism.
In an operation processing mechanism, an applied instruction is executed, and the result is transferred according to its destination in the format of a token as the argument data of the next instruction to be carried out.
Such an operation mechanism is called a data driven system since execution of an instruction is driven upon arrival of a token including data. FIG. 1 shows such the data driven principle. Referring to the left portion of FIG. 1, when an instruction requires two inputs, there are two input arcs at the nodes corresponding to this instruction. The number of output arcs is 1. When a token arrives to this node from the left and right input arcs, that instruction is fired, whereby data of the operation result (instruction executed result) is sent to the output arc as an output token as shown in the right portion of FIG. 1.
This data driven principle is described in, for example, "Joho Kagaku Jiten" (published by Iwanami Shoten, 1994), pp. 494-497.
FIG. 2 schematically shows a structure of a conventional data-driven processor. This data-driven processor 400 includes a dynamic firing control (matching) mechanism (FC: Firing Control) 402, an operation processing mechanism (FP: Function Processor) 108, a program storage mechanism (PS: Program Store) 104, and a data input/output control unit (I/O: Input Output Control) 102. These basic functions are connected via a circular pipeline.
A cascade connection of a temporary storage mechanism by a hand shake type data transfer control system shown in FIG. 3 is employed as the basic structure for data transfer and processing by this circular pipeline.
Referring to FIG. 3, the data transfer mechanism includes data latches 410 and 412 provided preceding and succeeding a hardware primitive 414, C-elements 406 and 408 for carrying out hand shake type data transfer control to provide a timing signal for data transfer with respect to data latches 410 and 412. By a continuous provision of such structures, data is transferred sequentially through each data latch, and a process with respect that data is carried out by hardware primitive 414.
A data packet which is a working packet of a physical level is selected autonomously by a self-route select function in this structure to be subjected to a process sequentially by each functional element. By passing through this flow path, execution of information processing proceeds autonomously. By introducing such a system, a system bus, a system clock, central control mechanism, and the like are all removed from a data-driven processor. In other words, control of the entire system is completely decentralized.
The processing speed of such a data-driven processor essentially depends upon the internal circuit structure of the C-element (self timing type transfer control element) shown in FIG. 3 and the natural scientific characteristics of a device. The internal circuit structure of C-element 406 (or 408) is shown in FIG. 4. This exemplified C-element shown in FIG. 4 determines the data transfer timing using the preceding and succeeding C-elements and signals CI, CO, RI, and RO. In response, a control pulse CP of the data latch is output.
Therefore, by determining the internal circuit structure of the C-element, the time required for processing in an interstage process between a cascade-connected network of a temporary storage mechanism by a hand shake type data transfer control system under this condition can be defined.
In a general operation process of a data-driven processor, the operation is divided into operation elements of lower levels, which are processed in a plurality of stages. This is called a pipeline division process.
However, such a pipeline division process cannot be carried out in dynamic firing control mechanism 402 shown in FIG. 2. The reason will be described hereinafter.
In a data-driven processor, the execution rate of a program and the amount of hardware of the entire computer are greatly dependent upon how the firing control mechanism of argument data applied as a packet is realized. More specifically, reduction of the hardware required for the firing control mechanism and the processing time of matching are one of the most important issues in the system design of a data-driven processor.
A firing control mechanism basically requires the following three functions.
(1) Determination is made whether an input packet is argument data of a 2-input instruction. When the packet is directed to a 1-input instruction, it bypasses the process for matching.
(2) When the input packet is directed to a 2-input instruction, determination is made whether the packet of the other party has already arrived or not.
(3) If the packet of the other party has already arrived, it is read out as the other argument data, and then transferred to the operation processing mechanism together with the input packet. When the packet of the other party has not yet arrived, the input packet is stored in the matching memory.
An input packet towards a data-driven processor is formed of a destination specifying portion and a data portion. Structures of a data packet are shown in FIGS. 14 and 15. FIG. 14 shows the format of a packet 510 in a path other than that starting from a firing control mechanism to an operation processing mechanism. FIG. 15 shows the format of a data packet 512 transferred from a firing control mechanism to an operation processing mechanism.
Referring to the exemplary formats of FIGS. 14 and 15, the destination specifying portion of an input packet towards a data-driven processor generally includes destination information for identifying a matching party such as an element processor number, an instruction storage address (node number) ND, generation number GN and the like, as well as other information such as the type of packet and matching conditions or the like. The data portion is generally formed of the data type and data per se. In FIGS. 14 and 15, the left data is indicated as LD and the right data is indicated as RD. In a firing control mechanism, the above-described firing control function is carried out using this destination information.
A logic circuit diagram of a firing control mechanism is shown in FIGS. 6 and 7. The circuits shown in FIGS. 6 and 7 are joined as shown in FIG. 5. This firing control mechanism is firing control mechanism 402 shown in FIG. 2.
Referring to FIGS. 6 and 7, firing control mechanism 402 includes C-elements 420, 422, 424, 426, 428 and 430, data latches 440, 442, 444, 446, 448, 450, 452 and 454, an FC-adapted 2-input instruction execution packet detection unit 254, a firing control main processing unit 188, and logic gate circuits 460, 462, and 464 for carrying out various functions such as discarding and erasing a data packet, and handshake type transfer control.
A process in dynamic firing control mechanism 402 shown in FIGS. 6 and 7 is carried out as set forth in the following. When a data packet is latched in data latch 440, FC-adapted 2-input instruction execution packet detection unit 254 detects whether this packet is an FC-adapted 2-input instruction execution packet and generates a flag FR representing the determination result. Flag FR is provided to firing control main processing unit 188 with the input packet data.
The data processed by firing control main processing unit 188 and the input packet data are selectively extracted and discarded by data latches 450, 452, and 454 to result in an output packet. This output packet is provided from data latch 454.
A logic circuit diagram of firing control main processing unit 188 is shown in FIGS. 9 and 10 which are to be joined as shown in FIG. 8.
Referring to FIGS. 9 and 10, firing control main processing unit 188 includes C-element for firing control main processing unit 270 and C-element 288, data latches 276, 280, 286 and 296, an access adjustment unit 282 for a matching memory, a matching memory 284, a hash collision detection unit 290, a firing detail detection unit 292, a destination information select unit 294, and inverters 272 and 274.
Firing control main processing unit 188 operates as set forth in the following. Flag FR indicating whether the input packet is a 2-input instruction execution packet or not and the required data from the data packet provided to firing control mechanism are applied to firing control main processing unit 188. The input packet is passed through if it is a 1-input packet. More specifically, when a signal value applied to a WWB terminal of C-element for firing control main processing unit 270 shown in FIG. 9 takes a value indicating a 1-input packet, a short interstage processing time mode is selected, and the input packet is subjected to a through process.
The following process must be carried out in one stage of an interstage process when the input packet is a 2-input instruction execution packet. The process includes a reading and writing process from and to a matching memory, and a process associated thereto. The details will be described hereinafter.
Data is read out from matching memory 284 using a pair of bits in the destination specifying portion of the input packet as the address. The structure of the data in matching memory 184 is shown in FIG. 11.
Hash collision detection unit 290 compares the hash overflow destination specifying portion in matching memory 284 with the hash overflow destination specifying portion in the input packet to determine whether a hash collision has occurred or not.
Firing detail detection unit 292 generates a flag triggering a firing control process when the input packet is a 2-input instruction execution packet, no hash collision has occurred, and the data read out from the memory is valid (PRE flag=1). This flag is provided to matching memory 284 via matching memory access adjusting unit 282.
Then, the data in the input packet and data read out from matching memory 284 are collected and output as a packet. Also, the data in the appropriate address of matching memory 284 is invalidated. More specifically, the value of the valid (PRE) flag of that address is nullified (0). Determination can be made whether data is valid or not by identifying the value of this PRE flag at the time of readout.
When the input packet is a 2-input instruction execution packet, the data read out from matching memory 284 is valid, and hash collision has occurred, a packet is output with a valid value of the hash collision flag. This packet circulates the circular pipeline to be provided again to the firing control mechanism, whereby a firing processing is carried out again.
When the input packet is a 2-input instruction execution packets, and the data read out from matching memory 284 is invalid, the data value in the input packet is written into an appropriate address of matching memory 284. Here, the PRE flag of this address is set valid.
The above-described process of a firing detail detection, reading out of the data from a matching memory for hash collision detection, and data writing for various processes must be carried out within one stage of an interstage process. Therefore, and also since the physical propagation delay time of a logic element is finite, the interstage processing time required for the above-described process including the reading/writing operation of data from a matching memory must be set longer than those of other standard processing units. Other standard processing units include processing units capable of a pipeline division process.
C-element for firing control main processing unit 270 shown in FIG. 9 is a C-element provided for adjustment of such a processing time. A logic circuit diagram of C-element 270 is shown in FIG. 13.
Referring to FIG. 13, C-element 270 includes C-elements 470 and 472, data latches 480, 482 and 484, logic gate circuits 490, 492, 494, 496, 498, 500, 502, 504 and 506. The manner of connection therebetween is as illustrated.
When a packet requiring a writing operation towards matching memory 284 is processed in the circuit of FIG. 13, i.e. when the input to terminal WWB is 0, a long interstage processing time mode is selected. It is to be noted that terminal WWB receives an inverted value of flag FR by inverter 274 as shown in FIG. 9. This means that the case where the signal of terminal WWB indicates 0 is equivalent to the case where the input packet is a 2-input instruction execution packet.
When a packet that does not require writing to match memory 284 is processed, i.e. the input to terminal WWB is 1, the short interstage processing time mode is selected. More specifically, when the input packet is a 1-input instruction packet, an interstage processing time of a standard C-element is selected.
In view of the foregoing, there is a possibility that the process in firing control main processing unit 188 becomes the bottleneck in the overall processing time of the entire driven type processor depending upon how the long interstage processing time mode is selected over time. For example, when a long interstage processing time mode is continuously selected, the processing time required for the entire system is rate-determined depending upon the processing speed of firing control main processing unit 188.
This fact pertains even when the mechanism related to hash collision of the firing control mechanism is removed. An example of a structure of a matching memory in such case is shown as a matching memory 284a in FIG. 12.
The tendency of the amount of hardware required for the structure of a firing control mechanism can be envisioned as set forth in the following. In a firing control mechanism, matching memory 284 (refer to FIGS. 11 and 12) for generating a data pair is used. The memory capacity required for this memory is in principle: EQU 2.sup.b1 .times.b2
where b1 and b2 indicate the number of bits of the destination specifying portion and the data portion, respectively. The required memory capacity increases in an exponential functional manner in response to increase of the number of bits of the destination specifying unit.
For firing-control in a firing control mechanism, the processes of reading out data from a matching memory, writing data into a memory when there is no matching data, and a process associated thereto must be carried out in one stage of a pipeline. Therefore, this process may become the bottleneck of the process of the entire data-driven processor. It is therefore desirable to improve the entire processing rate by carrying out the process as fast as possible. It is also desirable to suppress the increase of hardware as low as possible required for the structure of the firing control mechanism. It is most preferable to reduce the amount of hardware.